Reverse string¶
Time: O(N); Space: O(1); easy
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: s = [“h”,“e”,“l”,“l”,“o”]
Output: [“o”,“l”,“l”,“e”,“h”]
Example 2:
Input: s = [“H”,“a”,“n”,“n”,“a”,“h”]
Output: [“h”,“a”,“n”,“n”,“a”,“H”]
Hints:
The entire logic for reversing a string is based on using the opposite directional two-pointer approach!
1. Two Pointers (Iteration) [O(N),O(1)]¶
In this approach, two pointers are used to process two array elements at the same time. Usual implementation is to set one pointer in the beginning and one at the end and then to move them until they both meet.
Sometimes one needs to generalize this approach in order to use three pointers, like for classical Sort Colors problem.
Algorithm
Set pointer left at index 0, and pointer right at index n - 1, where n is a number of elements in the array.
While left < right:
Swap s[left] and s[right].
Move left pointer one step right, and right pointer one step left.
[37]:
class Solution1(object):
"""
Time: O(N) to swap N/2 element.
Space: O(1), it's a constant space solution.
"""
def reverseString(self, s):
"""
:type s: List[str]
:rtype: Do not return anything, modify list in-place instead.
"""
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right - 1
[38]:
sol = Solution1()
s = ["h","e","l","l","o"]
sol.reverseString(s)
assert s == ["o","l","l","e","h"]
s = ["H","a","n","n","a","h"]
sol.reverseString(s)
assert s == ["h","a","n","n","a","H"]
2. Swap elements¶
[39]:
class Solution2(object):
"""
Time: O(N), to swap N/2 elements.
Space: O(N)
"""
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
string = list(s)
i, j = 0, len(string) - 1
while i < j:
string[i], string[j] = string[j], string[i]
i += 1
j -= 1
return ''.join(string)
[40]:
sol = Solution2()
s = "hello"
assert sol.reverseString(s) == "olleh"
s = "Hannah"
assert sol.reverseString(s) == "hannaH"
3. Recursion (In-Place) [O(N),O(N)]¶
Does in-place mean constant space complexity?
No. By definition, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure.
The tricky part is that space is used by many actors, not only by data structures. The classical example is to use recursive function without any auxiliary data structures.
Is it in-place? Yes.
Is it constant space? No, because of recursion stack.
Algorithm
Here is an example. Let’s implement recursive function helper which receives two pointers, left and right, as arguments.
Base case: if left >= right, do nothing.
Otherwise, swap s[left] and s[right] and call helper(left + 1, right - 1).
To solve the problem, call helper function passing the head and tail indexes as arguments: return helper(0, len(s) - 1).
[41]:
class Solution3(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: Do not return anything, modify list in-place instead.
"""
def helper(left, right):
if left < right:
s[left], s[right] = s[right], s[left]
helper(left + 1, right - 1)
helper(0, len(s) - 1)
[42]:
sol = Solution3()
s = ["h","e","l","l","o"]
sol.reverseString(s)
assert s == ["o","l","l","e","h"]
s = ["H","a","n","n","a","h"]
sol.reverseString(s)
assert s == ["h","a","n","n","a","H"]
4. String slice [O(N),O(N)]¶
[43]:
class Solution4(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: List[str]
"""
return s[::-1]
# same as s.reverse()
[44]:
sol = Solution4()
s = ["h","e","l","l","o"]
res = sol.reverseString(s)
assert res == ["o","l","l","e","h"]
s = ["H","a","n","n","a","h"]
res = sol.reverseString(s)
assert res == ["h","a","n","n","a","H"]